package algorithm.floyd;

import java.util.Arrays;

/**
 * 弗洛伊德算法：解决图的所有顶点到其他顶点最短距离
 * 迪杰斯特拉算法：解决图的某一个顶点到其他顶点最短距离
 *
 * @author jack.wu
 * @version 1.0
 * @date 2020-04-08
 */
public class FloydAlgorithm {
    static final int N = 65335;

    public static void main(String[] args) {
        char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int[][] matrix = {{0, 5, 7, N, N, N, 2},
                          {5, 0, N, 9, N, N, 3},
                          {7, N, 0, N, 8, N, N},
                          {N, 9, N, 0, N, 4, N},
                          {N, N, 8, N, 0, 5, 4},
                          {N, N, N, 4, 5, 0, 6},
                          {2, 3, N, N, 4, 6, 0}};
        Graph graph = new Graph(vertex, matrix);
        graph.floyd();
        graph.show();
    }

}

class Graph {
    /**
     * 顶点数组
     */
    private char[] vertex;
    /**
     * 邻接矩阵
     */
    private int[][] dis;
    /**
     * 前驱
     */
    private int[][] pre;

    public Graph(char[] vertex, int[][] matrix) {
        this.vertex = vertex;
        this.dis = matrix;
        this.pre = new int[vertex.length][vertex.length];
        for (int i = 0; i < pre.length; i++) {
            Arrays.fill(pre[i], i);
        }
    }

    /**
     * 显示dis和pre
     */
    public void show() {
        char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        for (int k = 0; k < vertex.length; k++) {
            for (int i = 0; i < vertex.length; i++) {
                System.out.print(vertex[pre[k][i]] + "\t");
            }
            System.out.println();
            for (int i = 0; i < vertex.length; i++) {
                System.out.print("(" + vertex[k] + "到" + vertex[i] + "的最短距离：" + dis[k][i] + ")");
            }
            System.out.println();
            System.out.println();
        }
    }


    /**
     * 弗洛伊德算法
     */
    public void floyd() {
        int len;
        // 中间顶点
        for (int k = 0; k < vertex.length; k++) {
            // 出发顶底
            for (int i = 0; i < vertex.length; i++) {
                // 到达顶点
                for (int j = 0; j < vertex.length; j++) {
                    // lik + lkj l:距离 i：出发顶点 j：到达顶点
                    len = dis[i][k] + dis[k][j];
                    if (len < dis[i][j]) {
                        // 如果通过中间顶点的距离小于直接距离 则更新距离和更新前驱顶点
                        dis[i][j] = len;
                        pre[i][j] = pre[k][j];
                    }
                }
            }
        }
    }
}